package _2022.hot100._139_单词拆分;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author： YHSimon
 * @date： 2022-04-30 15:05
 */
public class Solution {

    // 动态规划
    public boolean wordBreak2(String s,List<String> wordDict){
        Set<String>  wordDictSet = new HashSet(wordDict);
        boolean[] dp=new boolean[s.length()+1];
        dp[0]=true;
        for(int i=1;i<s.length();i++){
            for(int j=0;j<=i;j++){
                if(dp[j]&&wordDictSet.contains(s.substring(j, i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }


    //回溯
    public boolean wordBreak(String s, List<String> wordDict){
        if (s.equals("")||s.length()==0){
            return true;
        }
        boolean flag=false;
        for(String str:wordDict){
            if(s.length()>=str.length()&&s.substring(0,str.length() ).equals(str)){
                flag=wordBreak(s.substring(str.length()),  wordDict);
                if(flag){
                    break;
                }
            }
        }
        return flag;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        List<String> wordDict=new ArrayList<>();
        // wordDict.add("cats");
        // wordDict.add("dog");
        // wordDict.add("sand");
        // wordDict.add("and");
        // wordDict.add("cat");
        // wordDict.add("leet");
        // wordDict.add("code");
        wordDict.add("apple");
        wordDict.add("pen");
        System.out.println(s.wordBreak("applepenapple", wordDict));
    }

}
